package com.zlei.code.binaryTree.traversal;

import com.zlei.code.binaryTree.TreeNode;

import java.util.Stack;

/**
 * https://blog.csdn.net/qiuxinfa123/article/details/84880786
 * 二叉树的中序遍历
 * @Author leizhang76
 * @Date 2021/2/20 9:55
 */
public class MidOrder {

    /**
     * 递归的中序遍历
     * @param node
     */
    public void mid(TreeNode node){
        if (node==null){
            return;
        }
        mid(node.left);
        System.out.println(node.val);
        mid(node.right);
    }


    /**
     * 二叉树的非递归中序遍历
     * 1、先将根节点入栈
     * 2、将当前节点的所有左孩子节点入栈
     * 3、访问栈顶元素，如果栈顶元素存在右孩子，则继续第二步
     * 4、重复2、3步，直到栈为空并且所有的节点都被访问
     * @param root
     */
    public void inOrder2(TreeNode root){
        if (root==null){
            return;
        }
        TreeNode temp=root;
        Stack<TreeNode> stack=new Stack<>();
        while (temp!=null&&!stack.isEmpty()){
            //1、将根节点入栈
            //2、将所有左孩子节点入栈
            while (temp!=null){
                stack.push(temp);
                temp=temp.left;
            }
            //3、访问栈顶元素
            temp=stack.pop();
            System.out.println(temp.val);
            //4、如果栈顶元素存在右孩子，则将右孩子赋值给temp,也就是右孩子入栈
            if (temp.right!=null){
                temp=temp.right;
            }else {
                //否则，将temp置为null,表示下次要访问的是栈顶元素
                temp=null;
            }
        }

    }

}









